package NQueens;

public class Queens {
    /*
    用一个一维数组存放结果{0，4，7，5，2，6，1，3}
    表示第一个皇后放在第1列，第二个皇后放在第5列...
     */
    int max = 8;
    int[] queen = new int[max];
    static int count = 0;//to count how many answers

    public static void main(String[] args) {
        Queens queens = new Queens();
        queens.check(0);
        System.out.println("Total: " + count + " answers");
    }

    //put queens
    private void check(int n) {
        if (n == max) {//if put No.n queen,presented queens which <n has been put correctly
            print();
            return;
        }
        for (int i = 0; i < max; i++) {
            queen[n] = i;
            if (judge(n)) {
                check(n + 1);
            }
        }
    }

    //judge queens whether conflict or not
    private boolean judge(int n) {//when put No.n queen,check conflict
        for (int i = 0; i < n; i++) {
            if (queen[i] == queen[n]/*No.i queen and No.n queen is in the same line*/
                    || Math.abs(n - i) == Math.abs(queen[n] - queen[i])) {
                return false;
            }
        }
        return true;
    }

    //to print correct answers
    private void print() {
        count++;
        for (int i = 0; i < queen.length; i++) {
            System.out.print(queen[i] + " ");
        }
        System.out.println();
    }
}

